Some printing features such as signature printing require that an image be rotated by 90 degrees. The simplest method of performing a rotation would be to have a page buffer constructed of a two-dimensional memory array that could be addressed by column or by row. The data would be written into the buffer with the words along the column direction and then read out with the words along the row direction.
This rotation could be considered to take zero time since the same number of read and write operations must be performed as with an unrotated image. The only thing that must be done is to change the mode of memory from column mode to row mode (i.e. rotated mode). Also, by changing the mode of the memory while loading objects into the buffer, images may be constructed of rotated and unrotated objects. Unfortunately, the memory devices needed to build a page buffer with both row and column access do not yet exist commercially.
Some inventions handle this requirement by the provision of a specially designed memory which can read in the image data words in one direction and read out in an orthogonal direction. However, such special purpose memories are expensive, and tend to have small capacities.
A method and circuit for producing these rotations at high speed without the necessity of special memory hardware is described in commonly owned patent applications Ser. No. 07/453,738 entitled "Method To Rotate A Bitmap Image 90 Degrees" and Ser. No. 07/721,797, "Parallel Rotation Algorithm", which are incorporated by reference herein. In its simplest form, this prior invention can be described with reference to a 4 by 4 bit block of binary pixels in memory arranged as four horizontal words of four bits each, which must be rotated 90 degrees. See FIGS. 1 through 4 of the above mentioned "Method To Rotate A Bitmap Image 90 Degrees" patent application.
The method can be explained as the addition of the rotation of the bits within each 4 by 4 bit block and the rotation of the blocks of the whole image. To rotate bits within a block, the first 4 bit word is loaded into the first line of a 4 by 4 bit buffer. The next word is circularly rotated upward one bit and loaded into the second line of the buffer. The third word is circularly shifted two bits and loaded into the third line of the buffer and the fourth line is circularly shifted three bits and loaded into the fourth line of the buffer. At this point a vertical line in the original image is still a vertical line in the buffer, but a horizontal line in the original is now a diagonal line in the buffer.
Since the buffer is implemented from "by 1" devices, any bit in each device is addressable independently of the other devices, and a bit in one word in the buffer can be loaded into any bit of the four words of memory. Therefore, if the bits in the buffer are addressed along diagonal lines parallel to the diagonal line in the buffer and loaded into single words of the memory, the diagonal line in the buffer will become a vertical line at the output. Continuing with addressing the bits along diagonal lines, the vertical line in the buffer will become a diagonal line at the output. The output four words, prior to storage in memory, are shifted to line up the diagonal bits into a horizontal line. Since this line started as a vertical line, it can be seen that the 4 by 4 bit block has now been completely rotated 90 degrees. To rotate the blocks within the image, a simple addressing algorithm provides that the blocks read out of the block buffer are read in the correct sequence.
This method requires the number of bits in each row and column to be equal and to be a power of two. With an image assumed to be 12,288 bits per line by 5,122 lines before rotation, the page buffer needs an address space of 256 Megabits, arranged as 16,384 pixels by 16,384 lines. However, only 64 Megabits of memory are needed at any one given time to store the image. It would be a significant improvement if the number of blocks of buffer memory required to rotate an image could be reduced to the number of blocks actually required to store the image, regardless of the image shape.